package com.sheng.leetcode.year2022.month09.day03;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/05
 *
 * 646. 最长数对链
 *
 * 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
 * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
 * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
 *
 * 示例：
 *
 * 输入：[[1,2], [2,3], [3,4]]
 * 输出：2
 * 解释：最长的数对链是 [1,2] -> [3,4]
 *
 * 提示：
 *
 * 给出数对的个数在 [1, 1000] 范围内。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-length-of-pair-chain
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0646 {

    @Test
    public void test01() {
        int[][] pairs = {{1,2}, {2,3}, {3,4}};
        System.out.println(new Solution().findLongestChain(pairs));
    }
}

class Solution {
    public int findLongestChain(int[][] pairs) {
        int length = pairs.length;
        // 结果集，并赋初值1
        int[] ints = new int[length];
        Arrays.fill(ints, 1);
        // 对二维数组pairs的第一个元素进行从小到大的排序
        Arrays.sort(pairs, Comparator.comparingInt(o -> o[0]));
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < i; j++) {
                // 如果存在i前面的数组中的后一个元素，小余i数组的第一个元素，则加入
                if (pairs[i][0] > pairs[j][1]) {
                    ints[i] = Math.max(ints[i], ints[j] + 1);
                }
            }
        }
        return ints[length - 1];
    }
}
//class Solution {
//    public int findLongestChain(int[][] pairs) {
//        // 暴力破解超时
//        int length = pairs.length;
//        int max = 0;
//        for (int i = 0; i < length; i++) {
//            List<Integer> list = new ArrayList<>();
//            list.add(pairs[i][1]);
//            loop(pairs, list);
//            max = Math.max(max, list.size());
//        }
//        return max;
//    }
//
//    public void loop(int[][] pairs, List<Integer> list) {
//        boolean flag = true;
//        while (flag) {
//            int index = -1;
//            int min = Integer.MAX_VALUE;
//            for (int i = 0; i < pairs.length; i++) {
//                if (pairs[i][0] > list.get(list.size() - 1) && pairs[i][1] < min) {
//                    index = i;
//                    min = pairs[i][1];
//                }
//            }
//            if (index == -1) {
//                flag = false;
//            } else {
//                list.add(pairs[index][1]);
//            }
//        }
//    }
//}
